class Solution
{
 public:
  // 递归版
  // int Fibonacci(int n)
  // {
  //   int result;
  //   if (n == 1 || n == 2)
  //     return 1;
  //   else
  //   {
  //     result = Fibonacci(n - 1) + Fibonacci(n - 2);
  //   }

  //   return result;
  // }

  // 动态规划版
  int Fibonacci(int n)
  {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int numfn1 = 0, numfn2 = 1;
    int currentnum;
    for (int i = 2; i <= n; ++i)
    {
      currentnum = numfn1 + numfn2;
      numfn1 = numfn2;
      numfn2 = currentnum;
    }
    return currentnum;
  }
};